#include "train.h"

//设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
//
//请实现 KthLargest 类：
//
//KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
//int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。


//class KthLargest {
//public:
//    typedef pair<int, int> PII;
//    set<PII> s;
//    int tot = 0, K;
//    KthLargest(int k, vector<int>& nums) { //获取堆顶元素
//        K = k;
//        for (auto x : nums) // 遍历数组
//            add(x);  //插入x
//    }
//
//    int add(int val) {
//
//        s.insert(PII(val, tot++));
//
//        if (s.size() > K)  s.erase(s.begin());//弹出
//        return s.begin()->first;
//    }
//};


class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>>q;
    int k;

    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (auto x : nums)
        {
            add(x);
        }
    }

    int add(int val) {
        q.push(val);
        if (q.size() == k) q.pop();
        return q.top();
    }
};
